/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow, *fast;
    slow = fast = head;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next;
        fast = fast->next;
    }
    return slow;
}

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL, *next = head;
    while(next){
        struct ListNode* obj = next->next;
        next->next = prev;
        prev = next;
        next = obj;
    }
    return prev;
}

void reorderList(struct ListNode* head) {
    struct ListNode* head1 = middleNode(head);
    struct ListNode* head2 = reverseList(head1);

    struct ListNode* prev = head, *next1 = prev->next, *cur = head2, *next2 = cur->next;
    while(next2){
        prev->next = cur;
        cur->next = next1;
        prev = next1;
        next1 = next1->next;
        cur = next2;
        next2 = next2->next;
    }
}

/*
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。*/